package dp

/*
给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。


*/
func findTargetSumWays(nums []int, target int) int {
	// 遍历搜索啊
	var traverse func(i int, pathSum int)
	var res int
	traverse = func(i int, pathSum int) {
		if i == len(nums) {
			if pathSum == target {
				res++
			}
			//得到一组结果
			// res ++
			return
		}
		// 单层逻辑
		// 可以选择两种操作
		// path = append(path, nums[i])
		// 进入下一层
		traverse(i+1, pathSum+nums[i])
		// 回溯
		// path = path[:len(path)-1]

		// -
		// path = append(path, 0-nums[i])
		traverse(i+1, pathSum-nums[i])

	}
	traverse(0, 0)
	return res
}

// dp
func findTargetSumWays1(nums []int, target int) int {
	// 1 确定dp[i]的意义  ： 表示和为i的不同表达式个数
	sum := 0
	for _, v := range nums {
		sum += v
	}
	if (sum+target)%2 == 1 {
		return 0 // 无解
	}
	if abs(target) > sum {
		return 0 // 即将所有数字都变为正/负，都无法达到要求
	}
	// left = (target+sum)/2
	target = (target + sum) / 2
	// 背包问题 容量为target 01
	dp := make([]int, target+1)
	// 物品重量和价值为nums[i]
	// 递推公式 ：
	// 填满容量为j-nums[i]的背包，有dp[j-nums[i]]种方法
	// dp[3]  dp[0]+dp[1]+dp[2]
	dp[0] = 1 //容量0，只有一种装法
	for i := 0; i < len(nums); i++ {
		for j := target; j >= nums[i]; j-- {
			// if dp[j] < dp[j-nums[i]]+nums[i] {
			// 求装满背包有几种方法，一般如下递推公式
			dp[j] += dp[j-nums[i]]

		}
	}
	return dp[target]
}
func abs(a int) int {
	if a < 0 {
		return 0 - a
	}
	return a
}
